class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int ans=-1, cnt=0;
        for(int num:nums)
        {
            if(cnt==0) ans=num, cnt=1;
            else cnt+=ans==num?1:-1;
        }
        cnt=0;
        for(int num:nums) if(num==ans) cnt++;
        return cnt>nums.size()/2?ans:-1;
    }
};